package HuaWeiOd.AA;

import java.util.Scanner;

/**
 * 现在有n个容器服务，服务的启动可能有一定的依赖性(有些服务启动没有依赖)，其次服务自身启动加载会消耗些时间。
 * <p>
 * 给你一个nxn 的二维矩阵 useTime，其中 useTime[i][i]=10 表示服务i自身启动加载需要消耗10s，useTime[i][j]=1 表示服务i 启动依赖服务i 启动完成，useTime[i][k]=0，表示服务i 启动不依赖服务 k其实 0<= i,j，k< n。服务之间启动没有循环依赖(不会出现环)，若想对任意一个服务i进行集成测试(服务追身也需要加载)，求最少需要等待多少时间。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入服务总量 n.
 * <p>
 * 之后的 n 行表示服务启动的依赖关系以及自身启动加载耗时
 * <p>
 * 最后输入 k 表示计算需要等待多少时间后可以对服务 k 进行集成测试
 * <p>
 * 其中 1 <= k <=n. 1<=n<=100
 * <p>
 * 输出描述
 * <p>
 * 最少需要等待多少时间(s)后可以对服务 k 进行集成测试
 * <p>
 * 示例1
 * <p>
 * 输入:
 * <p>
 * 3
 * <p>
 * 5 0 0
 * <p>
 * 1 5 0
 * <p>
 * 0 1 5
 * <p>
 * 3
 * <p>
 * 输出:
 * <p>
 * 15 作者：天生完美 https://www.bilibili.com/read/cv21829268?from=search 出处：bilibili
 *
 * @author caihe
 * @date 2023/4/12 10:32
 */
public class 微服务的集成测试 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        int k = sc.nextInt();

        System.out.println(fun(arr, k - 1));
    }

    public static int fun(int[][] arr, int k) {
        // 当前服务器的启动耗时
        int sum = arr[k][k];

        int time = 0;
        for (int i = 0; i < arr.length; i++) {
            // 计算服务器所依赖的服务器耗时
            if (i != k && arr[k][i] == 1) {
                time = Math.max(time, fun(arr, i));
            }
        }
        return sum + time;
    }


}
